//We write the integers of nums1 and nums2 (in the order they are given) on two
//separate horizontal lines. 
//
// Now, we may draw connecting lines: a straight line connecting two numbers num
//s1[i] and nums2[j] such that: 
//
// 
// nums1[i] == nums2[j]; 
// The line we draw does not intersect any other connecting (non-horizontal) lin
//e. 
// 
//
// Note that a connecting lines cannot intersect even at the endpoints: each num
//ber can only belong to one connecting line. 
//
// Return the maximum number of connecting lines we can draw in this way. 
//
// 
//
// Example 1: 
//
// 
//Input: nums1 = [1,4,2], nums2 = [1,2,4]
//Output: 2
//Explanation: We can draw 2 uncrossed lines as in the diagram.
//We cannot draw 3 uncrossed lines, because the line from nums1[1]=4 to nums2[2]
//=4 will intersect the line from nums1[2]=2 to nums2[1]=2.
// 
//
// 
// Example 2: 
//
// 
//Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
//Output: 3
// 
//
// 
// Example 3: 
//
// 
//Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
//Output: 2 
//
// 
// 
// 
//
// Note: 
//
// 
// 1 <= nums1.length <= 500 
// 1 <= nums2.length <= 500 
// 1 <= nums1[i], nums2[i] <= 2000 
// 
// Related Topics 数组 
// 👍 122 👎 0


package leetcode.editor.cn;

public class UncrossedLines {
    public static void main(String[] args) {
        Solution solution = new UncrossedLines().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxUncrossedLines(int[] nums1, int[] nums2) {
            //即计算数组num1和num2的最长公共子序列的长度
            //二维动态规划
            int m = nums1.length;
            int n = nums2.length;
            int[][] dp = new int[m + 1][n + 1];//初始值均为0
            for (int i = 1; i <= m; i++) {
                int num1 = nums1[i - 1];
                for (int j = 1; j <= n; j++) {
                    int num2=nums2[j-1];
                    if (num1==num2){
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else {
                        dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            return dp[m][n];

        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
